BZOJ 4443 小凸玩矩阵

Description

小凸和小方是好朋友,小方给小凸一个N*M(N<=M)的矩阵A,要求小秃从其中选出N个数,其中任意两个数字不能在同一行或同一列,现小凸想知道选出来的N个数中第K大的数字的最小值是多少。

Input

第一行给出三个整数N,M,K
接下来N行,每行M个数字,用来描述这个矩阵

Output

如题

Sample Input

3 4 2
1 5 6 6
8 3 4 3
6 8 6 3

Sample Output

3

Hint

1<=K<=N<=M<=250,1<=矩阵元素<=10^9

Solution

二分一下匈牙利判一下
(匈牙利枚到nWA了两次……心累)

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include<bits/stdc++.h>

#define maxn 250+5
#define set(a,b) memset(a,(b),sizeof(a))

using namespace std;

typedef long long ll;

int w[maxn][maxn];
int vis[maxn],match[maxn];
int n,m,k,ans;

bool find(int x,int lim)
{

for(int i=1;i<=m;i++)
if( w[x][i]<=lim && !vis[i] ){
vis[i]=1;
if( !match[i] || find(match[i],lim) ){
match[i]=x;
return true;
}
}
return false;
}

bool hungary(int x)
{

int cnt=0;
set(match,0);
for(int i=1;i<=n;i++){
set(vis,0);
cnt+=find(i,x);
}
return cnt>=n-k+1;
}

void binary()
{

int l=1,r=1e9;
while( l!=r ){
int mid=(l+r)/2;
if( hungary(mid) ) r=mid;
else l=mid+1;
}
ans=l;
}

int main()
{

#ifndef ONLINE_JUDGE
freopen("4443.in","r",stdin);
freopen("4443.out","w",stdout);
#endif
scanf("%d%d%d",&n,&m,&k);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
scanf("%d",&w[i][j]);
binary();
printf("%d",ans);
return 0;
}